package lc.数组;

/**
 * @description: 接雨水
 * @author: qian
 * @createDate: 2021/9/21
 */
public class Math42 {

    /**
     * 找到左右两边最大值中的较小的值去减去当前位置上的值就是该位置上能存的最大水量
     *
     * @param height
     * @return
     */

    public int trap(int[] height) {

//        int n = height.length;
//        int leftMax = -1, rightMax = -1;
//        int water = 0;
//        int [] d = new int[n];
//        for (int i = 0; i < n; i++) {
//
//            leftMax = Math.max(leftMax,height[i]);
//            d[i] = leftMax;
//        }
//
//        for (int i = n - 1; i >= 0; i--) {
//
//            rightMax = Math.max(rightMax,height[i]);
//            d[i] = Math.min(d[i],rightMax);
//            water += (d[i] - height[i]);
//        }
//        return water;

        int n = height.length;
        int leftMax = -1, rightMax = -1, water = 0;
        int i = 0, j = n - 1;

        while(i <= j) {
            leftMax = Math.max(leftMax,height[i]);
            rightMax = Math.max(rightMax,height[j]);
            if (leftMax > rightMax) water += (rightMax - height[j--]);
            else water += (leftMax - height[i++]);
        }
        return water;
    }
}
